package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

/**
 * 剑指offer-面试3
 * 二维数组中的查找
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请
 * 完成一个函数，输入这样一个二位数组和一个整数，判断数组中是否含有该整数。
 */
public class Mianshi3 {

    public static void main(String[] args) {
        int[][] matrix = {{1, 5, 8},{2, 6, 10}, {4, 7, 17}};
        boolean result = findLeftdown(matrix, 3,3, 4);
        System.out.println(result);
    }

    public static boolean findMatrix(int[][] matrix, int rows, int clos, int num){
        boolean result = false;
        int low = clos;

        lable:
        for (int i = 0; i < rows; i++){
            for (int j = 0; j < low; j++) {
                if (matrix[i][j] > num){
                    low = j;
                    break;
                } else if (matrix[i][j] ==  num){
                    result = true;
                    break lable;
                }
            }
        }

        return result;
    }

    public static boolean findRightup(int[][] matrix, int rows, int cols, int num) {
        boolean result = false;

        if (matrix != null && rows > 0 && cols > 0) {
            int row = 0;
            int col = cols - 1;
            while (row < rows && col >= 0) {
                if (matrix[row][col] == num) {
                    result = true;
                    break;
                } else if (matrix[row][col] > num) {
                    col--;
                } else {
                    row++;
                }
            }
        }

        return result;
    }

    public static boolean findLeftdown(int[][] matrix, int rows, int cols, int num) {
        boolean result = false;

        if (matrix != null && rows > 0 && cols > 0) {
            int row = rows - 1;
            int col = 0;
            while (row >= 0 && col < cols) {
                if (matrix[row][col] == num) {
                    result = true;
                    break;
                } else if (matrix[row][col] < num) {
                    col++;
                } else {
                    row--;
                }
            }
        }

        return result;
    }
}
